Branch-and-price guided search for integer programs with an application to the multicommodity fixed-charge network flow problem

Title: Branch-and-price guided search for integer programs with an application to the multicommodity fixed-charge network flow problem
Creator: Hewitt, Mike; Nemhauser, George; Savelsbergh, Martin W. P.
Relation: INFORMS Journal on Computing Vol. 25, Issue 2, p. 302-316
Publisher Link: http://dx.doi.org/10.1287/ijoc.1120.0503
Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
Resource Type: journal article
Date: 2013
Description: We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in network flow type applications, to help define the restrictions that are solved. In addition, local search around the current best solution is incorporated to enhance overall performance. The approach is parallelized and computational experiments on a classical problem in network design demonstrate its efficacy.
Subject: integer programming; column generation; local search; multicommodity fixed-charge network flow
Identifier: http://hdl.handle.net/1959.13/939513
Identifier: uon:12829
Identifier: ISSN:1091-9856
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format